package demo.node;


/**
 * @author : feixiang.li
 * @since : 2025-09-19 09:44
 */
public class Solution_21 {

    public ListNode partition(ListNode head, int x) {
        // 用于记录 等于x的节点
        ListNode lowHead = null, lowTail = null;
        ListNode highHead = null, highTail = null;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val < x) {
                if (lowHead == null) {
                    lowHead = cur;
                    lowTail = lowHead;
                } else {
                    lowTail.next = cur;
                    lowTail = cur;
                }
            } else {
                if (highHead == null) {
                    highHead = cur;
                    highTail = highHead;
                } else {
                    highTail.next = cur;
                    highTail = cur;
                }
            }
            cur = cur.next;
        }
        // 低的节点拼接 高的节点
        if (lowTail != null) {
            lowTail.next = highHead;
        }
        if (highTail != null) {
            highTail.next = null;
        }
        if (lowHead != null) {
            return lowHead;
        }else {
            return highHead;
        }
    }

    public static void main(String[] args) {
//
//        ListNode node1 = new ListNode(1);
//        ListNode node2 = new ListNode(4);
//        ListNode node3 = new ListNode(3);
//        ListNode node4 = new ListNode(2);
//        ListNode node5 = new ListNode(5);
//        ListNode node6 = new ListNode(2);
//        node1.next = node2;
//        node2.next = node3;
//        node3.next = node4;
//        node4.next = node5;
//        node5.next = node6;
//        ListNode partition = new Solution_21().partition(node1, 3);
//        while (partition != null) {
//            System.out.println(partition.val);
//            partition = partition.next;
//        }
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        node2.next = node1;
        ListNode partition = new Solution_21().partition(node2, 2);
        while (partition != null) {
            System.out.println(partition.val);
            partition = partition.next;
        }
    }
}
